package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import java.util.HashMap;
import java.util.Map;

/**
 * @author By ZengPeng
 */
public class 力扣_116_填充每个节点的下一个右侧节点指针 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_116_填充每个节点的下一个右侧节点指针().connect(new Node()));
    }

    /**
    题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
     如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     初始状态下，所有 next 指针都被设置为 NULL。

     示例 1：
     输入：root = [1,2,3,4,5,6,7]
     输出：[1,#,2,3,#,4,5,6,7,#]
     解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

     示例 2:
     输入：root = []
     输出：[]

    分析：【P 💗💖💘💝】
        1.递归+map:记录住每一层的最后一个节点，当再次遇到这一层的节点时，这个节点指向它
            -- 执行用时：1 ms, 在所有 Java 提交中击败了71.00%的用户 。空间：O(h),时间：O(n)
        大神：root.right.next = root.next.left ;上一层帮助下一层建立连接
            -- 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 。空间：O(1),时间：O(n)
    边界值 & 注意点：
       1.
     **/
    public Node connect(Node root) {
        //大神：root.right.next = root.next.left
        if(root==null) return root;
        Node pro = root;
        //循环条件是当前节点的left不为空，当只有根节点
        //或所有叶子节点都出串联完后循环就退出了
        while (pro.left!=null){
            Node tmp = pro;//这一样遍历下去
            while (tmp!=null){
                tmp.left.next = tmp.right;
                if(tmp.next!=null) {
                    tmp.right.next = tmp.next.left;
                }
                //继续向右遍历
                tmp=tmp.next;
            }
            pro = pro.left;
        }
        //1.递归+map:记录住每一层的最后一个节点，当再次遇到这一层的节点时，这个节点指向它
//        Map<Integer, Node> map= new HashMap<>();
//        dfs(root,1,map);
        return root;
    }

    private void dfs(Node root, int level, Map<Integer, Node> map) {
        if(root==null) return;
        Node level_node = map.get(level);
        if(level_node!=null)level_node.next=root;
        map.put(level,level_node);
        dfs(root.left,level+1,map);
        dfs(root.right,level+1,map);
    }
}
